#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/23 13:53
# ===========================================
#       题目名称： 30. 串联所有单词的子串
#       题目地址： https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    """
        实现思路：
            1、按字典排序 对切割的单词 和 要比对的单词排个序 然后进行比对
    """

    def findSubstring(self, s, words):
        """
            实现有问题
        """
        words.sort()
        word_len = len(words[0])  # 当个单词的长度
        words_len = len(words)  # 单词组的长度
        res = []
        i = 0
        while i < len(s):
            if i + word_len * words_len > len(s):
                break
            new_s = s[i:i + word_len * words_len]
            new_words = []
            for j in range(0, len(new_s), word_len):
                new_words.append(new_s[j: j + word_len])
            new_words.sort()
            if words == new_words:
                res.append(i)
            i += 1
        return res


if __name__ == '__main__':
    s = Solution()
    # [0,9]
    print(s.findSubstring(s="barfoothefoobarman", words=["foo", "bar"]))
    # []
    print(s.findSubstring(s="wordgoodgoodgoodbestword", words=["word", "good", "best", "word"]))
    # [6,9,12]
    print(s.findSubstring(s="barfoofoobarthefoobarman", words=["bar", "foo", "the"]))
    # [0,1,2,3,4,5,6,7,8,9,10]
    print(s.findSubstring(s="aaaaaaaaaaaaaa", words=["aa", "aa"]))
